package com.mgq.algorithm;

/**
 * @author MaGuangQi
 * @description https://leetcode-cn.com/problems/powx-n/
 * lettcode第50题,计算x^n x的n次方
 * @date 2020-06-30 21:37
 **/
public class PowerX {
    /**
     * 解法一: 暴力解法
     */
    public double myPower1(double x, int n) {
        long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        double ans = 1;
        for (long i = 0; i < N; i++) {
            ans = ans * x;
        }
        return ans;
    }

    /**
     * 解法二: 使用递归
     */
    public double myPower(double x, long n) {
        if (n == 0) {
            return 1;
        }
        if (n < 0) {
            //2^-n =1/2^n
            //如果是int,需要考虑-n越界的情况.所以改为long
            return 1 / myPower(x, -n);
        }
        //奇数 x的n次方就等于 x的二分之n乘以x的二分之n再乘以x(奇数时少了一个n)
        if (n % 2 != 0) {
            return x * myPower(x * x, n / 2);
        }
        //奇数第二种写法  奇数的时候不就相当于 x* x^(n-1)
        /*if (n % 2 != 0) {
            return x * myPower(x, n -1);
        }*/

        //偶数 x的n次方就等于 x的二分之n乘以x的二分之n
        return myPower(x * x, n / 2);
    }

    /**
     * 解法三: 使用循环
     */
    public double myPower3(double x, long n) {
        if (n < 0) {
            x = 1 / x;
            n = -n;
        }
        double power=1;
        while (n > 0) {
            if ((n & 1) == 1) {
                //奇数
                power=power*x;
            }
            x=x*x;
            //n右移以为
            n>>=1;
        }
        return power;
    }

    public static void main(String[] args) {
        PowerX powerX = new PowerX();

        System.out.println(powerX.myPower3(2,4));
    }
}
